class Solution {
public:
    int integerReplacement(int n){
        // 时间O(logN) 空间O(1)
        int ret = 0;
        while(n != 1)
        {
            if(n % 2 == 0)
            {
                n =  n / 2;
                ++ret;
            }
            else
            {
                ret += 2; // 下面操作都是两步
                if(n == 3)
                    break;
                else if(n % 4 == 1) // ......01
                    n /= 2; // 和减1除2结果一样
                else // ......01
                    n = n / 2 + 1; // 和加1除2结果一样，防溢出
            }
        }
        return ret;
    }
};